package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 940. 不同的子序列 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/14 9:28
 */
public class DistinctSubseqII {

    public static void main(String[] args) {
        DistinctSubseqII test = new DistinctSubseqII();

        // 87
//        String str = "abababab";

        // 3
//        String str = "aaa";

        // 6
//        String str = "aba";

        //
        String str = Utils.getStr(2000, 'a', 'z');

        int i = test.distinctSubseqII(str);
        System.out.println(i);
    }

    public int distinctSubseqII(String s) {
        int length = s.length();
        long[] arr = new long[26];
        long item = 0;
        for (int i = 0; i < length; i++) {
            int t = s.charAt(i) - 'a';
            long v = (item + 1) - arr[t];
            if (v < 0) {
                v += 1000000007;
            }
            arr[t] = (arr[t] + v) % 1000000007;
            item = (item + v) % 1000000007;
        }
        return (int) item;
    }

}
